As VLSI circuits have become both more dense and more complex, they have become increasingly difficult to test.
In particular, the inability to access internal nodes of a VLSI circuit because of the density and microscopic size of the circuit components has made it necessary to test such circuits only; by accessing the input and output terminals of the circuit chip. Usually this is done by applying a set of vectors as an input to the circuit and looking for an appropriate set of outputs. While this technique is useful for some types of VLSI circuits it tends not to be particularly useful with sequential circuits, which are circuits with memory elements or registers, and in which an earlier state of the circuit is important to the final state. Such sequential circuits can be represented as finite state machines. In such circuits, it is advantageous to make certain memory elements controllable and observable for reliable testing, advantageously by testing in the manner of a combinational test circuit.
One established method is to insert scan hardware after the desired functional circuit has been synthesized. In this technique, critical memory elements whose performance is to be observed are provided with auxiliary circuitry that is normally dormant but that is activated on command to interconnect the critical memory elements into a shift register that is then scanned so that the performance of individual memories can be observed. This full scan technique has the disadvantage that it tends to require considerable additional circuitry that consumes valuable space that might otherwise have been used for the functional circuit. Although there have been modifications of this approach to provide partial scan, at the expense of reduced reliability, this has not always been a completely satisfactory solution to the problem.
A more recent trend has been to consider testability during the logic synthesis of the circuit. This technique has been described in a paper entitled "Finite State Machine Synthesis with Embedded Test Function," Journal of Electronic Testing: Theory and Applications, Vol. 1 pp. 221-228 (1990). It has also been the subject of U.S. Pat. No. 5,228,040 which issued on Jul. 13, 1993, filed by V. D. Agrawal and K. T. Cheng who also authored the identified paper.
This approach involves the selected incorporation of a test function into the state diagram of the finite state machine appropriate for the desired VLSI circuit. For testing, the augmented state diagram is then implemented as the desired functional circuit and the test function is used to test the entire circuit. There are usually several choices for the test function and several ways in which a chosen test function can be incorporated into the state diagram of a finite state machine and these choices can have a significant impact on the area and performance of the final implementation.
In particular, the incorporation of the test function or a test machine into the object finite state machine, hereinafter more simply the object machine, can become complex when the object machine has a significant number of states. In general, for n states of the test machine there are n! ways of embedding the test function into the object machine when a new input is added, because each object machine state can be mapped onto any one of the n states. Moreover, the area overhead can be higher than that of full scan unless the states of the state machine are mapped efficiently onto the states of the object machine. In particular, it is advantageous if the test machine can be embedded into the object machine without the need for an additional input line, although this is not usually the case. Additionally, for a complicated functional VLSI circuit, such as one that might involve hundreds or thousands of memory elements, the design of an appropriate finite state machine for the entire circuit becomes so formidable a project as usually to prove impractical.